一道很机智的题。
问最少有多少路径。
设点的坐标为x,y,本题其实是找满足x1<=x2<=x3…且y1<=y2<=y3…..的最少序列。先排序其中之一，另外一边用贪心的思想暴力搞一搞。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
int x[900],y[900],r[900];
int cmp(int a,int b)
{
if(x[a]==x[b])return y[a]<y[b];
return x[a]<x[b];
}
int c[60];
int has(int a)
{
int k=0;
for(int i=1;i<=a;i++)
if(c[i])k=i;
return k;
}
int main()
{
int a,b;
int n=0;
while(scanf("%d%d",&a,&b),~a)
{
if(!a)
{
sort(r,r+n,cmp);
mem(c,0);
int cnt=0;
for(int i=0;i<n;i++)
{
int e=y[r[i]];
int t=has(e);
if(!t)
{
c[e]++,cnt++;
}
else c[t]--,c[e]++;
}
printf("%d\n",cnt);
n=0;
}
else
{
x[n]=a,y[n]=b;
r[n]=n++;
}
}
}
|
EOF